package com.example.tree;

/**
 * Created by Quincy on 2018/9/12.
 * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 */
public class BalanceTree {

    /**
     * 就是对于每一个节点，它的右子树深度减去左子树的深度的绝对值必须是小于2才行。
     * 对于这个深度差，我们也叫做平衡因子。
     * */
    public class TreeNode{
        int val;
        TreeNode left = null;
        TreeNode right = null;
        TreeNode (int val){
            this.val = val;
        }
    }

    public static int TreeDepth(TreeNode root) {
        if (root == null) return 0;

        int leftDepth = TreeDepth(root.left) + 1;
        int rightDepth = TreeDepth(root.right) + 1;
        return Math.max(leftDepth, rightDepth);

    }

    public static boolean isBalance1(TreeNode node){
        if (node == null) return true;
        int left = TreeDepth(node.left);
        int right = TreeDepth(node.right);
        int dif = left - right;
        if (dif > 1 || dif < -1)
            return false;
        return isBalance1(node.left)&&isBalance1(node.right);
    }

    public boolean isBalance2(TreeNode node){
        int depth = 0;
        return isBalance2(node, depth);
    }

    /**
     *  如果我们用后序遍历的方式遍历二叉树的每个结点，
     *  在遍历一个结点之前我们就已经遍历了它的左右子树。
     *  只要在遍历每个结点的时候我们记录它的深度（某一节点的深度等于它到叶结点的路径的长度），
     *  我们就可以一边遍历一边判断每个结点是不是平衡二叉树
     * */

    public boolean isBalance2(TreeNode node, int depth){
        if (node == null){
            depth = 0;
            return true;
        }
        int left = 0, right = 0;
        if (isBalance2(node.right, right) && isBalance2(node.left, left)){
            int diff = left - right;
            if (diff <= 1 && diff >= -1){
                depth = Math.max(left, right);
                return true;
            }
        }
        return false;
    }
}
